home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / MacPerl 5.0.3 / MacPerl Source ƒ / Perl5 / x2p / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-26  |  4.7 KB  |  242 lines  |  [TEXT/MPS ]
  1. /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $
  2.  *
  3.  *    Copyright (c) 1991, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  * $Log:    hash.c,v $
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include "EXTERN.h"
  13. #include "handy.h"
  14. #include "util.h"
  15. #include "a2p.h"
  16.  
  17. STR *
  18. hfetch(tb,key)
  19. register HASH *tb;
  20. char *key;
  21. {
  22.     register char *s;
  23.     register int i;
  24.     register int hash;
  25.     register HENT *entry;
  26.  
  27.     if (!tb)
  28.     return Nullstr;
  29.     for (s=key,        i=0,    hash = 0;
  30.       /* while */ *s;
  31.      s++,        i++,    hash *= 5) {
  32.     hash += *s * coeff[i];
  33.     }
  34.     entry = tb->tbl_array[hash & tb->tbl_max];
  35.     for (; entry; entry = entry->hent_next) {
  36.     if (entry->hent_hash != hash)        /* strings can't be equal */
  37.         continue;
  38.     if (strNE(entry->hent_key,key))    /* is this it? */
  39.         continue;
  40.     return entry->hent_val;
  41.     }
  42.     return Nullstr;
  43. }
  44.  
  45. bool
  46. hstore(tb,key,val)
  47. register HASH *tb;
  48. char *key;
  49. STR *val;
  50. {
  51.     register char *s;
  52.     register int i;
  53.     register int hash;
  54.     register HENT *entry;
  55.     register HENT **oentry;
  56.  
  57.     if (!tb)
  58.     return FALSE;
  59.     for (s=key,        i=0,    hash = 0;
  60.       /* while */ *s;
  61.      s++,        i++,    hash *= 5) {
  62.     hash += *s * coeff[i];
  63.     }
  64.  
  65.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  66.     i = 1;
  67.  
  68.     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  69.     if (entry->hent_hash != hash)        /* strings can't be equal */
  70.         continue;
  71.     if (strNE(entry->hent_key,key))    /* is this it? */
  72.         continue;
  73.     /*NOSTRICT*/
  74.     safefree((char*)entry->hent_val);
  75.     entry->hent_val = val;
  76.     return TRUE;
  77.     }
  78.     /*NOSTRICT*/
  79.     entry = (HENT*) safemalloc(sizeof(HENT));
  80.  
  81.     entry->hent_key = savestr(key);
  82.     entry->hent_val = val;
  83.     entry->hent_hash = hash;
  84.     entry->hent_next = *oentry;
  85.     *oentry = entry;
  86.  
  87.     if (i) {                /* initial entry? */
  88.     tb->tbl_fill++;
  89.     if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  90.         hsplit(tb);
  91.     }
  92.  
  93.     return FALSE;
  94. }
  95.  
  96. #ifdef NOTUSED
  97. bool
  98. hdelete(tb,key)
  99. register HASH *tb;
  100. char *key;
  101. {
  102.     register char *s;
  103.     register int i;
  104.     register int hash;
  105.     register HENT *entry;
  106.     register HENT **oentry;
  107.  
  108.     if (!tb)
  109.     return FALSE;
  110.     for (s=key,        i=0,    hash = 0;
  111.       /* while */ *s;
  112.      s++,        i++,    hash *= 5) {
  113.     hash += *s * coeff[i];
  114.     }
  115.  
  116.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  117.     entry = *oentry;
  118.     i = 1;
  119.     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
  120.     if (entry->hent_hash != hash)        /* strings can't be equal */
  121.         continue;
  122.     if (strNE(entry->hent_key,key))    /* is this it? */
  123.         continue;
  124.     safefree((char*)entry->hent_val);
  125.     safefree(entry->hent_key);
  126.     *oentry = entry->hent_next;
  127.     safefree((char*)entry);
  128.     if (i)
  129.         tb->tbl_fill--;
  130.     return TRUE;
  131.     }
  132.     return FALSE;
  133. }
  134. #endif
  135.  
  136. hsplit(tb)
  137. HASH *tb;
  138. {
  139.     int oldsize = tb->tbl_max + 1;
  140.     register int newsize = oldsize * 2;
  141.     register int i;
  142.     register HENT **a;
  143.     register HENT **b;
  144.     register HENT *entry;
  145.     register HENT **oentry;
  146.  
  147.     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
  148.     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
  149.     tb->tbl_max = --newsize;
  150.     tb->tbl_array = a;
  151.  
  152.     for (i=0; i<oldsize; i++,a++) {
  153.     if (!*a)                /* non-existent */
  154.         continue;
  155.     b = a+oldsize;
  156.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  157.         if ((entry->hent_hash & newsize) != i) {
  158.         *oentry = entry->hent_next;
  159.         entry->hent_next = *b;
  160.         if (!*b)
  161.             tb->tbl_fill++;
  162.         *b = entry;
  163.         continue;
  164.         }
  165.         else
  166.         oentry = &entry->hent_next;
  167.     }
  168.     if (!*a)                /* everything moved */
  169.         tb->tbl_fill--;
  170.     }
  171. }
  172.  
  173. HASH *
  174. hnew()
  175. {
  176.     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
  177.  
  178.     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
  179.     tb->tbl_fill = 0;
  180.     tb->tbl_max = 7;
  181.     hiterinit(tb);    /* so each() will start off right */
  182.     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
  183.     return tb;
  184. }
  185.  
  186. #ifdef NOTUSED
  187. hshow(tb)
  188. register HASH *tb;
  189. {
  190.     fprintf(stderr,"%5d %4d (%2d%%)\n",
  191.     tb->tbl_max+1,
  192.     tb->tbl_fill,
  193.     tb->tbl_fill * 100 / (tb->tbl_max+1));
  194. }
  195. #endif
  196.  
  197. hiterinit(tb)
  198. register HASH *tb;
  199. {
  200.     tb->tbl_riter = -1;
  201.     tb->tbl_eiter = Null(HENT*);
  202.     return tb->tbl_fill;
  203. }
  204.  
  205. HENT *
  206. hiternext(tb)
  207. register HASH *tb;
  208. {
  209.     register HENT *entry;
  210.  
  211.     entry = tb->tbl_eiter;
  212.     do {
  213.     if (entry)
  214.         entry = entry->hent_next;
  215.     if (!entry) {
  216.         tb->tbl_riter++;
  217.         if (tb->tbl_riter > tb->tbl_max) {
  218.         tb->tbl_riter = -1;
  219.         break;
  220.         }
  221.         entry = tb->tbl_array[tb->tbl_riter];
  222.     }
  223.     } while (!entry);
  224.  
  225.     tb->tbl_eiter = entry;
  226.     return entry;
  227. }
  228.  
  229. char *
  230. hiterkey(entry)
  231. register HENT *entry;
  232. {
  233.     return entry->hent_key;
  234. }
  235.  
  236. STR *
  237. hiterval(entry)
  238. register HENT *entry;
  239. {
  240.     return entry->hent_val;
  241. }
  242.